"""
    左子树都比自己小
    右子树都比自己大
"""

class Node:
    def __init__(self, value):
        self.value = value
        self.lchild = None
        self.rchild = None
        self.parent = None # 父节点， 方便删除
    
    def __repr__(self):
        return self.value


class BSTree:
    def __init__(self):
        self.root = None
    
    def add(self, value):
        node = Node(value)
        if not self.root:
            self.root = node
            return 
        p = self.root
        while True:
            if value < p.value:
                if not p.lchild:
                    p.lchild = node
                    p.lchild.parent = p
                    break
                p = p.lchild
            elif value > p.value:
                if not p.rchild:
                    p.rchild = node
                    p.rchild.parent = p
                    break
                p = p.rchild
            else:
                break
        
    def __remove_1(self, node):
        """ 叶子节点 """
        if not node.parent:  # 没有父节点， 根节点
            self.root = None
        if node == node.parent.lchild: #是他父亲的左孩子
            node.parent.lchild = None
        else:
            node.parent.rchild = None
    
    def __remove_21(self, node):
        """ 只有一个左孩子 """
        if not node.parent: # 根节点
            # 根节点为当前节点的左孩子
            self.root = node.lchild
        elif node.parent.lchild.value == node.value:  # 是父节点的左节点， 那么所有子节点都比父节点小
            # 把当前节点的左孩子放到父节点的左孩子
            node.parent.lchild = node.lchild
            # 将当前节点的父节点作为子孩子的父节点
            node.lchild.parent = node.parent
        else:  # 是父节点的右节点， 所有子节点都比父节点大
            # 把当前节点的左孩子放到父节点的右孩子
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent
            
    def __remove_22(self, node):
        """ 只有一个右孩子 """
        if not node.parent: # 根节点
            self.root = node.rchild
        elif node.parent.lchild.value == node.value: # 是父节点的左节点， 那么所有子节点都比父节点小
            # 把当前节点的右孩子放到父节点的左孩子
            node.parent.lchild = node.rchild
            # 将当前节点的父节点作为子孩子的父节点
            node.rchild.parent = node.parent
        else:  # 是父节点的右节点， 所有子节点都比父节点大
            # 把当前节点的右孩子放到父节点的右孩子
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent
    
    def find_node(self, value):
        """ 寻找节点 """
        index = self.root
        while index:
            if index.value == value:
                return index
            elif value < index.value:
                index = index.lchild
            else: 
                index = index.rchild 
        return None
    
    def remove(self, value):
        node = self.find_node(value)
        if not node:
            return "该节点不存在"
        if not node.lchild and not node.rchild: # 叶子节点
            self.__remove_1(node) 
        elif not node.rchild:  # 只有左孩子
            self.__remove_21(node)
        elif not node.lchild:  # 只有右孩子
            self.__remove_22(node)
        else:  # 有两个孩子
            # 将右孩子的最左孩子替换当前节点删除， 最左孩子
            tmp = node.rchild
            while tmp.lchild:
                tmp = tmp.lchild
            # 替换
            node.value = tmp.value # 这个tmp 最多有一个右孩子
            if tmp.rchild:  # 有右孩子
                self.__remove_22(tmp)
            else:  # 没有孩子
                self.__remove_1(tmp)
        
    def breadth_first(self):
        """
            广度优先算法
        """
        queue = [self.root]
        while queue:
            index = queue.pop(0)
            if index.lchild:
                queue.append(index.lchild)
            if index.rchild:
                queue.append(index.rchild)
            print(index.value, end=" ")
    
    def pre_order(self, node):
        if not node:
            return
        print(node.value, end=" ")
        self.pre_order(node.lchild)
        self.pre_order(node.rchild)
    
    def in_order(self, node):
        if not node:
            return
        
        self.in_order(node.lchild)
        print(node.value, end=" ")
        self.in_order(node.rchild)
    
    def end_order(self, node):
        if not node:
            return
        
        self.end_order(node.lchild)
        self.end_order(node.rchild)
        print(node.value, end=" ")
   
    #           4
    #     2           6
    # 1       3   5       7
    #                         9
    #                     8


tree = BSTree()
tree.add(4)
tree.add(6)
tree.add(7)
tree.add(9)
tree.add(2)
tree.add(1)
tree.add(3)
tree.add(5)
tree.add(8)
print("层次遍历")
tree.breadth_first()
print()
print("===========")
print("先序")
tree.pre_order(tree.root)
print()
print("===========")
print("中序, 一定是排好序的")
tree.in_order(tree.root)

print()
print("===========")
print("删除")
tree.remove(4)
print("中序, 一定是排好序的")
tree.in_order(tree.root)
print()
tree.end_order(tree.root)